Tháng 8 ÂL năm Kiến Vũ thứ 2 (26), Quang Vũ đế - vừa đuổi Lưu Vĩnh ra khỏi Tuy Dương - sai Thái trung đại phu Phục Long cầm cờ tiết đi sứ 2 châu Thanh, Từ, các quận đều sợ hãi xin hàng, Bộ sai viên Duyện là Tôn Dục theo Long về Lạc Dương, dâng thư và hiến bào ngư. Tháng 11 ÂL, Đế lại sai Quang lộc đại phu Phục Long (được thăng chức) bái ông làm Đông Lai thái thú. Tháng 2 ÂL năm thứ 3 (27), Lưu Vĩnh nghe tin Long đến huyện Kịch, vội sai sứ lập Bộ làm Tề vương. Ông bèn bắt giữ Long, đề nghị ông ta cùng mình chiếm lấy 2 châu Thanh, Từ, Long cự tuyệt. Bộ sau đó giết Long mà nhận vương tước của Vĩnh.

Khi ấy, Quang Vũ đế bận rộn với Bành Sủng ở phía bắc, Lưu Vĩnh, Tần Phong ở phía nam, nên Bộ cát cứ miền đông, chiếm cứ 12 quận thuộc nước Tề. Bấy giờ Vĩnh đã chết, ông muốn lập con Vĩnh là Hu làm đế, tự làm Định Hán công, sắp đặt trăm quan. Vương Hoành can rằng: "Lương vương nhờ phụng mệnh Canh Thủy đế mà được người Sơn Đông quy thuận. Nay tôn lập con trai ông ta, sẽ khiến lắm kẻ nghi ngờ. Vả người Tề gian trá, cần bàn bạc kỹ lưỡng hơn." Bộ bèn thôi.